package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

/**
 * @author lchenglong
 * @date 2022/6/15
 */
public class 单链表的倒数第k个节点 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            ListNode head = ListNode.init(new int[]{1,2,3,4,5});
            ListNode listNode = solution.removeNthFromEnd(head, 2);
            ListNode.print(listNode);
        }
        public ListNode removeNthFromEnd(ListNode head, int n) {
            // 定义一个虚拟头结点,保证不越界
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            // 删除倒数第n个节点,需要先找到倒数第n+1个节点
            ListNode cursor = findFromEnd(dummy,n+1);
            // 删除第n个节点
            cursor.next = cursor.next.next;
            return dummy.next;
        }

        public ListNode findFromEnd(ListNode head,int k) {
            ListNode fast = head;
            // 快指针先走k个节点
            for (int i=0;i<k;i++){
                fast = fast.next;
            }
            ListNode slow = head;
            // 快慢指针同时走n-k个节点
            while (fast!=null) {
                fast = fast.next;
                slow = slow.next;
            }
            // 现在慢指针指向n-k个节点
            return slow;
        }
    }
}
